package util;
/**
 * 
 * @author ladjzero
 *
 */
public class EditDistance {
	public static int getDistance(String a, String b){
		int la = a.length();
		int lb = b.length();
		
		//if one string is void
		if( 0==la )
			return lb;
		if( 0==lb )
			return la;
		
		//build matrix
		int[][] distance = new int[la+1][lb+1];
		for(int i=0; i<la+1; i++)
			for(int j=0; j<lb+1; j++)
				distance[i][j]=0;
		for(int i=0; i<la+1; i++)
			distance[i][0] = i;
		for(int j=0; j<lb+1; j++)
			distance[0][j] = j;
		
		//compute
		for(int i=1; i<la+1; i++)
			for(int j=1; j<lb+1; j++){
				int temp = 1;
				if( a.charAt(i-1) == b.charAt(j-1))
					temp = 0;
				distance[i][j] = Math.min( Math.min(distance[i-1][j]+1, distance[i][j-1]+1), distance[i-1][j-1]+temp);
			}
		return distance[la][lb];
	}
	
	public static float getSimilartiy(String a, String b){
		return  1 - (float)( getDistance(a, b) )/Math.max(a.length(), b.length());
	}
}
